//
// Created by Vincent-Vic on 2020/4/07.
//

#ifndef DATAORGANIZATION_AVL_H
#define DATAORGANIZATION_AVL_H
#include <iostream>
#include <queue>
#include <cassert>
#include <list>
using namespace std;
template <typename Key,typename Value>
class AVL {
private:
    //内部节点
    struct Node{
        Key key;
        Value value;
        Node* left;
        Node* right;
        int height; //节点高度
        //内部节点初始化
        Node(Key key,Value value){
            this->key = key;
            this->value = value;
            this->left = this->right = NULL;
            this->height = 1 ;
        }
        //内部节点拷贝函数
        Node(Node* node){
            this->key = node->key;
            this->value = node->value;
            this->left = node->left;
            this->right = node->right;
            this->height = node->height;
        }
    };

    Node * root; //树根
    int count;  //个数

    //计算平衡因子
    int getBalanceFactor(Node* node){
        if (node == nullptr) return 0;
        return getHeight(node->left) - getHeight(node->right);
    }

    //判断以Node为根的二叉树是否是一颗平衡二叉树
    bool isBalanced(Node* node){
        if(node == nullptr) return true;
        int balanceFactor = getBalanceFactor(node);
        if (abs(balanceFactor) > 1) return false;
        return isBalanced(node->left) && isBalanced(node->right);
    }

    // 对节点y进行向右旋转操作，返回旋转后新的根节点x
    //        y                              x
    //       / \                           /   \
    //      x   T4     向右旋转 (y)        z     y
    //     / \       - - - - - - - ->    / \   / \
    //    z   T3                       T1  T2 T3 T4
    //   / \
    // T1   T2
    Node* rightRotate(Node* y){
        Node* x = y->left;
        Node* T3 = x->right;

        x->right = y;
        y->left = T3;

        //更新height
        y->height = max(getHeight(y->left),getHeight(y->right)) + 1 ;
        x->height = max(getHeight(x->left),getHeight(x->right)) + 1 ;
        return x;
    }


    // 对节点y进行向左旋转操作，返回旋转后新的根节点x
    //    y                             x
    //  /  \                          /   \
    // T1   x      向左旋转 (y)       y     z
    //     / \   - - - - - - - ->   / \   / \
    //   T2  z                     T1 T2 T3 T4
    //      / \
    //     T3 T4
    Node* leftRotate(Node* y) {
        Node* x = y->right;
        Node* T2 = x->left;

        x->left = y;
        y->right = T2;
        //更新height
        y->height = max(getHeight(y->left),getHeight(y->right)) + 1 ;
        x->height = max(getHeight(x->left),getHeight(x->right)) + 1 ;
        return x;
    }

    /**
     * 维护AVL平衡
     * @param node 失衡节点
     * @return 返回维护后的节点
     */
    Node* retainAVL(Node* node){

        if (node == nullptr)
            return nullptr;
        //更新height -- AVL
        // 高度为左右子节点高度最大值加1
        node->height =  1 + max(getHeight(node->left),getHeight(node->right));

        //计算平衡因子
        int balaceFactor = getBalanceFactor(node);
        //左侧产生的失衡 LL
        if(balaceFactor > 1 && getBalanceFactor(node->left) >= 0 )
            return rightRotate(node);//右旋转
        //右侧产生的失衡 RR
        if(balaceFactor < -1 && getBalanceFactor(node->right) <= 0 )
            return leftRotate(node);//左旋转
        //左侧的右侧产生的失衡 LR
        if(balaceFactor > 1 && getBalanceFactor(node->left) < 0 ){
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }
        //右侧的左侧产生的失衡 RL
        if(balaceFactor < -1 && getBalanceFactor(node->right) > 0 ){
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }

        return node;
    }

    /**
     * 以node为根递归插入
     * 形成左小右达到二叉树逻辑
     * 新增AVL
     * @param node 假设当前是根节点
     * @param key
     * @param value
     * @return 新的节点或者修改的点
     */
    Node* insert(Node* node , Key key , Value value){
        if (node == NULL){  //递归结束条件：当前节点为空，将节点插入
            count ++;   //节点增加
            return new Node(key,value); //创建新节点
        }
         if( key == node->key)  //如果key已经存在，替换key旧的值value
             node->value = value;
         else if(key < node->key) //key小于当前节点key 从左子树递归插入
             node->left = insert(node->left,key,value);
         else   //此时key大于当前节点key，向右子树递归插入
             node->right = insert(node->right,key,value);
        //维护平衡方法
        return retainAVL(node);
    }

    /**
     * 以node为根的二叉树中判断树中是否包含键值key的节点
     * @param node
     * @param key
     * @return
     */
    bool contain(Node* node,Key key){
        if (node == NULL) return false;
        if (key == node->key)   //如果键值与当前相等说明存在返回true
            return true;
        else if(key < node->key) //key 小于当前节点key 从左子树递归查找判断key是否存在
            return contain(node->left,key);
        else   //此时key大于当前节点key，向右子树递归查找判断key是否存在
            return contain(node->right,key);
    }

    /**
     * 以node为根的二叉树中查找节点
     * @param node
     * @param key
     * @return value地址
     */
    Value* search(Node* node,Key key){
        if (node == NULL)
            return NULL;

        if ( key == node->key)
            return &(node->value);
        else if(key < node->key) //key 小于当前节点key 从左子树递归查找判断key是否存在
            return search(node->left,key);
        else   //此时key大于当前节点key，向右子树递归查找判断key是否存在
            return search(node->right,key);

    }


    /**
     * 以node为根的二叉树 进行先序遍历
     * @param node
     */
    void preOrder(Node* node,vector<Key>& l){
        if (node != NULL){
            l.push_back(node->key);
            preOrder(node->left,l);
            preOrder(node->right,l);
        }

    }

    /**
     * 以node为根的二叉树 进行中序遍历 有序遍历二分搜索树
     * @param node
     */
    void inOrder(Node* node,vector<Key>& l){
        if (node != NULL){
            inOrder(node->left,l);
            l.push_back(node->key);
            inOrder(node->right,l);
        }

    }

    /**
     * 以node为根的二叉树 进行后续遍历
     * @param node
     */
    void postOrder(Node* node,vector<Key>& l){
        if (node != NULL){
            postOrder(node->left,l);
            postOrder(node->right,l);
            l.push_back(node->key);
        }

    }

    /**
    * 以node为根的二叉树 查找最大值
    * @param node
    */
    Node* maximum(Node* node){
        if (node->right == NULL)    //如果右节点不存在，当前节点即最大
            return node;
        return maximum(node->right); //存在右节点继续递归查找
    }

    /**
    * 以node为根的二叉树 查找最小值
    * @param node
    */
    Node* minimum(Node* node){
        if (node->left == NULL) //如果左节点不存在，当前节点即最小
            return node;
        return minimum(node->left); //存在左节点继续递归查找
    }

    /**
    * 以node为根的二叉树 删除最小值
    * @param node
    */
    Node* removeMin(Node* node){
        if (node->left == NULL) {   //如果左节点不存在，当前节点即最小
            Node* right = node->right ; //取用右节点代替
            delete node;    //删除节点 释放内存
            node = NULL;
            count --; //减少节点
            return right; //返回右节点作为最小节点或者NULL
        }
        node->left = removeMin(node->left); //递归删除
        return retainAVL(node); // 维护平衡
    }

    /**
    * 以node为根的二叉树 删除最大值
    * @param node
    */
    Node* removeMax(Node* node){
        if (node->right == NULL) {   //如果右节点不存在，当前节点即最大
            Node* left = node->left ; //取用左节点代替
            delete node;    //删除节点 释放内存
            node = NULL;
            count --; //减少节点
            return left; //返回左节点作为最小节点或者NULL
        }
        node->right = removeMax(node->right); //递归
        return retainAVL(node); // 维护平衡
    }

    //删除节点  Hubbard Deletion思想
    /**
    * 以node为根的二叉树 删除Key节点
    * @param node
    */
    Node* remove(Node* node,Key key){
        if (node == NULL) return NULL;
        Node* retNode = node;
        if (key < node->key)  //左数查找
            node->left = remove(node->left,key);
        else if (key > node->key)   //右树查找
            node->right = remove(node->right,key);
        else{ //找到的情况
            if (node->left == NULL){    //左孩子为空以及左右孩子都为空
                retNode = node->right; //右节点代替左节点的位置
                delete node;
                count --;
            }else if (node->right == NULL){ //右孩子为空
                retNode = node->left;//左节点代替右节点的位置
                delete node;
                count --;
            }else {
                //处理左右子树都存在的情况
                Node *successor = new Node(minimum(node->right)); //找到右子树的最小值替换删除的节点（拷贝）
                successor->right = removeMin(node->right);  //替换节点指向删除右子树最小值后的右子树（已经用来替换的节点）
                successor->left = node->left;   //替换节点指向用来左子树
                delete node;
                node = NULL;
                retNode = successor;
            }

        }
        //维护平衡方法
        return retainAVL(retNode);
    }

public:

    //构造函数
    AVL() {
        root = NULL;
        count = 0;
    }

    //析构函数销毁树
    virtual ~AVL() {
        destroy(root);
    }

    //树的数量
    int size(){
        return count;
    }

    //是否为空
    bool isEmpty(){
        return count ==0;
    }

    //得到树的高度---AVL新增
    int getHeight(Node* node){
        if ( node == NULL) return 0;
        return node->height;
    }
    //插入
    void insert(Key key,Value value){
        root = insert(root,key,value);
    }

    //判断键值是否存在
    bool contain(Key key){
        return contain(root,key);
    }

    //查找
    Value* search(Key key){
        return search(root,key);
    }

    //深度优先遍历(DFS) 先序遍历
    //返回遍历结果列表
    void preOrder(vector<Key>& l){
        preOrder(root,l);
    }

    //深度优先遍历(DFS) 中序遍历 有序遍历二分搜索树
    void inOrder(vector<Key>& l){
        inOrder(root,l);
    }

    //深度优先遍历(DFS) 后续遍历
    void postOrder(vector<Key>& l){
        postOrder(root,l);
    }

    //广度优先遍历(BFS) 层次遍历-队列实现
    void levelOrder(){
        queue<Node*> q; //存放Node的队列
        if (root == NULL){  //判断树空的情况
            cout<<"Tree Null"<<endl;
            return;
        }
        q.push(root);
        while ( !q.empty()){
            Node* node = q.front(); //取出第一个值
            q.pop(); //将第一个值出队，以便遍历下一个值
            cout<<node->key<<endl; //打印key值
            if (node->left) //如果左节点存在加入左子树的节点
                q.push(node->left);
            if (node->right) //如果右节点存在加入右子树的节点
                q.push(node->right);
        }

    }

    //判断是否是一个平衡二叉树
    bool isBalanced(){
        return isBalanced(root);
    }

    //判断是否是一棵二叉搜索树
    bool isBST(){
        vector<Key> keys;
        inOrder(keys);
        for (int i = 1; i < keys.size(); ++i)
            if (keys[i] < keys[i-1]) return false;
        return true;
    }

    //查找最大值
    Key maximum(){
        assert( count != 0);
        Node* maxNode = maximum( root);
        return maxNode->key;
    }

    //查找最小值
    Key minimum(){
        assert( count != 0);
        Node* minNode = minimum( root);
        return minNode->key;
    }

    //删除最小值
    void removeMin(){
        if (root)
            root = removeMin(root);
    }

    //删除最大值
    void removeMax(){
        if (root)
            root = removeMax(root);
    }

    //删除节点  Hubbard Deletion思想
    void remove(Key key){
        root = remove(root,key);
    }


    //销毁树 后序遍历的应用
    void destroy(Node* node){
        if (node != NULL){
            destroy(node->left);
            destroy(node->right);
            delete  node;
            node = NULL;
            count --;
        }
    }

};

//floor ceil rank select

#endif //DATAORGANIZATION_AVL_H
